/*
 * @lc app=leetcode.cn id=844 lang=cpp
 *
 * [844] 比较含退格的字符串
 *
 * https://leetcode-cn.com/problems/backspace-string-compare/description/
 *
 * algorithms
 * Easy (49.98%)
 * Likes:    397
 * Dislikes: 0
 * Total Accepted:    122.1K
 * Total Submissions: 244.8K
 * Testcase Example:  '"ab#c"\n"ad#c"'
 *
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * 
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "ab#c", t = "ad#c"
 * 输出：true
 * 解释：s 和 t 都会变成 "ac"。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "ab##", t = "c#d#"
 * 输出：true
 * 解释：s 和 t 都会变成 ""。
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：s = "a#c", t = "b"
 * 输出：false
 * 解释：s 会变成 "c"，但 t 仍然是 "b"。
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= s.length, t.length <= 200
 * s 和 t 只含有小写字母以及字符 '#'
 * 
 * 
 * 
 * 
 * 进阶：
 * 
 * 
 * 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
 * 
 * 
 */

// @lc code=start
// class Solution {
// public:
//     bool backspaceCompare(string s, string t) {
//         // int i = S.length() - 1, j = T.length() - 1;
//         // int skipS = 0, skipT = 0;

//         // while (i >= 0 || j >= 0) {
//         //     while (i >= 0) {
//         //         if (S[i] == '#') {
//         //             skipS++, i--;
//         //         } else if (skipS > 0) {
//         //             skipS--, i--;
//         //         } else {
//         //             break;
//         //         }
//         //     }
//         //     while (j >= 0) {
//         //         if (T[j] == '#') {
//         //             skipT++, j--;
//         //         } else if (skipT > 0) {
//         //             skipT--, j--;
//         //         } else {
//         //             break;
//         //         }
//         //     }
//         //     if (i >= 0 && j >= 0) {
//         //         if (S[i] != T[j]) {
//         //             return false;
//         //         }
//         //     } else {
//         //         if (i >= 0 || j >= 0) {
//         //             return false;
//         //         }
//         //     }
//         //     i--, j--;
//         // }
//         // return true;

//         int i = s.size()-1, j = t.size()-1;
//         int stepS = 0, stepT = 0;
//         while(i >= 0 || j >= 0){  
//             while(i >= 0){
//                 if(s[i] == '#'){
//                     i--;
//                     stepS++;
//                 } else if (stepS > 0) {
//                     i--;
//                     stepS--;
//                 } else {
//                     break;
//                 }
//             }
//             while(j >= 0){
//                 if(t[j] == '#'){
//                     j--;
//                     stepT++;
//                 } else if (stepT > 0) {
//                     j--;
//                     stepT--;
//                 } else {
//                     break;
//                 }
//             }
//             if(i >= 0 && j >= 0){
//                 if(s[i] != t[j]){
//                     return false;
//                 }
//             } else {
//                 if(i < 0 ^ j < 0){
//                     return false;
//                 }
//             }
//             i--;
//             j--;               
//         }
//         return true;
//     }

// };
// class Solution {
// public:
//     bool backspaceCompare(string s, string t) {
//         string s0 = process(s);
//         string t0 = process(t);
//         return s0 == t0;
//     }

//     string process(string s)
//     {
//         string res;
//         for(int i = 0; i < s.size(); i++){
//             if(s[i] != '#') res.push_back(s[i]);
//             else if(!res.empty()) res.pop_back();
//         }
//         return res;

//     }
// };

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string s0 = process(s);
        string t0 = process(t);
        return s0 == t0;
    }
    string process(string s){
        string res;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] != '#') res.push_back(s[i]);
            else if(!res.empty()) res.pop_back(); 
        }
        return res;
    }
};
// @lc code=end

